class Solution(object):
    def searchMatrix(self, matrix, target):
        def search(left, up, right, down):
            if left > right or up > down:
                return False
            if target < matrix[up][left] or target > matrix[down][right]:
                return False

            mid_col = (left + right) // 2
            row = up
            while row <= down and matrix[row][mid_col] <= target:
                if matrix[row][mid_col] == target:
                    return True
                row += 1
            return search(left, row, mid_col - 1, down) or search(mid_col + 1, up, right, row - 1)

        if not matrix or not matrix[0]:
            return False
        return search(0, 0, len(matrix[0]) - 1, len(matrix) - 1)

if __name__=="__main__":
    s = Solution()
    matrix = [
        [1, 4, 7, 11, 15],
        [2, 5, 8, 12, 19],
        [3, 6, 9, 16, 22],
        [10, 13, 14, 17, 24],
        [18, 21, 23, 26, 30]
    ]
    print(s.searchMatrix(matrix, 5))   # True
    print(s.searchMatrix(matrix, 20))  # False